// 线性表(a1, a2, a3,.,an)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，
// 完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换,
// 若找不到，则将其插入表中并使表中元素仍递增有序。

#pragma once
#include "vector"
#include "iostream"
/**
 * 插入的模板可以记一下
*/
void insert(std::vector<int> &A, int value, int index)
{
    A.resize(A.size() + 1);
    for (int i = A.size() - 1; i > index; i--)
    {
        A[i] = A[i - 1];
    }
    A[index] = value;
}
/**
 * 二分查找的模板可以记一下
*/
bool findInRange(std::vector<int> &A,
                 const int &x,
                 const int &minIndex,
                 const int &maxIndex, int &ret_finalPos)
{
    if (minIndex == maxIndex)
    {
        ret_finalPos = minIndex;
        if (A[minIndex] == x)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    int middle = (minIndex + maxIndex) / 2;
    if (A[middle] > x)
    {
        return findInRange(A, x, minIndex, middle - 1, ret_finalPos);
    }
    else if (A[middle] < x)
    {
        return findInRange(A, x, middle + 1, maxIndex, ret_finalPos);
    }
    else
    {
        return middle;
    }
}

void fastFind(std::vector<int> &A, int x)
{
    int ret_finalPos = -1;
    auto findIndex = findInRange(A, x, 0, A.size() - 1, ret_finalPos);
    std::cout << "finalPos " << ret_finalPos
              << "\r\n";
    if (findIndex)
    {
        std::cout << "find index:" << findIndex << "\r\n";
        std::cout << "find value:" << A[findIndex] << "\r\n";
    }
    else
    {
        std::cout << "not find"
                  << "\r\n";
        if (A[ret_finalPos] > x)
        {
            insert(A, x, ret_finalPos);
        }
        else
        {
            insert(A, x, ret_finalPos + 1);
        }
        std::cout << "after insert: ";
        for (auto i : A)
        {
            std::cout << i << ",";
        }
        std::cout << "\r\n";
    }
}

int main()
{
    std::vector<int> vec1; // vec2, vec3;

    //init data
    for (int i = 0; i < 100; i++)
    {
        if (i % 2 == 0)
        {
            // if (i < 50)
            {

                vec1.push_back(i);
            }
        }
        else
        {
            // vec2.push_back(i);
        }
    }
    fastFind(vec1, 9);
    // for (int i = 0; i < vec1.size(); i++)
    // {
    //     std::cout << vec1[i] << ",";
    // }
    // std::cout << "\r\n";
    // for (int i = 0; i < vec2.size(); i++)
    // {
    //     std::cout << vec2[i] << ",";
    // }
    // std::cout << "\r\n";
    // ///////////////////////////////////////////////////
    // combineAB2C(vec1, vec2, vec3);
    // for (int i = 0; i < vec3.size(); i++)
    // {
    //     std::cout << vec3[i] << ",";
    // }
    // std::cout << "\r\n";
    return 0;
}